#include <math.h>
#include <cmath>
#include <vector>
#include <stdlib.h>

struct point
{
   double x;
   double y;
};

double sl(point &a, point &b)
{
   return pow((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y), 2);
}

double distance(point &o, point &a, point &b)
{
   double AO = sl(a, o);
   double BO = sl(b, o);
   double AB = sl(a, b);
   if (AO >= BO + AB)
      return sqrt(BO);
   if (BO >= AO + AB)
      return sqrt(AO);
   return pow((b.x - a.x) * (a.y - o.y) - (b.y - a.y) * (a.x - o.x), 2) /  AB;
}

void douglas_peucker(int first, int last, const double &EPS, std::vector<point> &polyline, std::vector<bool> &outline)
{
   double d;
   double max = -1.0;
   int id = -1;
   for (int i = first + 1; i < last; i++)
   {
      d = distance(polyline[i], polyline[first], polyline[last]);
      if (d > EPS && d > max)
      {
         max = d;
         id = i;
      }
   }
   if (id == -1)
      return;
   else
      outline[id] = true;
   douglas_peucker(first, id, EPS, polyline, outline);
   douglas_peucker(id, last, EPS, polyline, outline);
}
